Cloud datacenters are becoming increasingly popular, as they offer computing resources for multiple tenants at a very low cost on an attractive pay-as-you-go model. Many small and medium businesses are turning to these cloud datacenters, not only for occasional large computational tasks, but also for their IT jobs. This helps them eliminate the expensive, and often very complex, task of building and maintaining their own infrastructure. The operators of these multi-tenant cloud datacenters can provide a cost-effective Infrastructure as a Service (“IaaS”), because they can time-multiplex the physical infrastructure among a large number of tenants. The advent of mature CPU virtualization techniques makes it possible to convert dedicated, and often underutilized, physical servers into Virtual Machines (“VMs”) that run in an IaaS provider's cloud datacenter.
To fully realize the benefits of resource sharing, these cloud datacenters must scale to huge sizes. The larger the number of tenants, and the larger the number of VMs, the better the chances for multiplexing, which in turn achieves better resource efficiency and cost savings. Increasing the scale alone, however, cannot fully minimize the total cost as a great deal of expensive human effort is required to configure the equipment, to operate it optimally, and to provide ongoing management and maintenance. A good fraction of these costs reflect the complexity of managing a multi-tenant network, which must scale to large numbers of tenants, hosts and VMs, support large numbers of addresses, and provide ample bandwidth between the VMs of any tenant. Most currently available network architectures are not capable to support multi-tenancy in an efficient and scalable fashion and usually compromise low cost or ease of operation.